#ifndef __TABLERO_H__
#define __TABLERO_H__

#include <iostream>
using namespace std;

#include "../aed2/aed2.h"

namespace aed2{

    typedef unsigned int Casilla;
    typedef unsigned int Continente;

    template<class T>
    class Tablero {

    public:
    
        class ItDestinos;
        struct CasillaMov;
    
        /**
         * Crea un tablero nuevo con un continente y una casilla en este.
         *
         * PRE : Ninguna
         * POST: Se crea el tablero.
         *
         * @Parametros: Ninguno
         * @Devuelve: Nada
         */ 
        Tablero();

        /**
         * Destruye el tablero.
         *
         * PRE : Ninguna
         * POST: Se destruye el tablero.
         *
         * @Parametros: Ninguno
         * @Devuelve: Nada
         */ 
        ~Tablero();

        /**
         * Agrega una casilla nueva conectada con la casilla parámetro, en el
         * mismo continente.
         *
         * PRE : La casilla cas está definida y no tiene definido al movimiento
         *  de salida mvue
         * POST: Se agregó una casilla conectada con la indicada de ida y vuelta
         * @Parámetros:
         *    cas : casilla de referencia
         *    mida: movimiento entre la casilla nueva y la de referencia
         *    mvue: movimiento entre la casilla de referencia y la nueva
         * @Devuelve: Una referencia al Tablero
         */ 
        void Contener(Casilla cas, T& mida, T& mvue);

        /**
         * Agrega una casilla nueva conectada con la casilla parámetro, en un
         * nuevo continente
         * 
         * PRE : La casilla cas está definida y no tiene definido al movimiento
         *  de salida mueve
         * POST: Se agregó una casilla conectada de ida y vuelta con la casilla
         *  indicada.
         * @Parámetros:
         *       cas : casilla de referencia
         *       mida: movimiento entre la casilla nueva y la de referencia
         *       mvue: movimiento entre la casilla de referencia y la nueva
         * @Devuelve: Una referencia al Tablero
         */ 
        void Agregar(Casilla cas, T& mida, T& mvue);

        /**
         * Agrega una conexión de una casilla a otra.
         * 
         * PRE : La casillas están definidas y 'cas1' no tiene definido el
         *  movimiento de salida 'mov'
         * POST: Se agregó conexión desde la casilla1 a la casilla2, con nombre
         *  'mov'
         * @Parámetros:
         *       cas1 : casilla de origen
         *       cas2 : casilla destino
         *       mov  : movimiento entre cas1 y cas2 (cas1 -mov-> cas2)
         * @Devuelve: Una referencia al Tablero
         */
        void Movilizar(Casilla cas1, Casilla cas2, T& mov);
        
        /**
         * Agrega una conexión doble de una casilla a otra.
         * 
         * PRE : La casillas están definidas y 'cas1' no tiene definido el
         *  movimiento de salida 'mov'
         * POST: Se agregó conexión desde la casilla1 a la casilla2, con nombre
         *  'mov'
         * 
         * @Parámetros:
         *       cas1 : una casilla
         *       cas2 : la otra casilla
         *       mida : movimiento entre cas1 y cas2  (cas1 -mida-> cas2)
         *       mvue : movimiento entre cas2 y cas1  (cas1 -mvue-> cas2)
         * @Devuelve: Una referencia al Tablero
         */ 

        void Conectar(Casilla cas1, Casilla cas2, T& mida, T& mvue);
        
        /**
         * Devuelve un conjunto con los continentes del Tablero.
         * 
         * PRE : Ninguna
         * POST: El resultado tiene el conjunto de los continentes del Tablero.
         * 
         * @Parámetros: Ninguno
         * @Devuelve: Una referencia constante al conjunto de continentes
         */ 
        Conj<Continente> Continentes() const;
        
        /**
         * Devuelve si dos casillas están conectadas directamente.
         * 
         * PRE : Las dos casillas son parte del tablero.
         * POST: El resultado es un bool con la conexión .
         * 
         * @Parámetros:
         *       cas1 : una casilla
         *       cas2 : la otra casilla
         * @Devuelve: Un bool indicando si están conectadas
         */ 
        bool Conectadas(Casilla cas1, Casilla cas2) const;

        /**
         * Devuelve los movimientos de salida a partir de una casilla.
         * 
         * PRE : La casilla es parte del tablero.
         * POST: El resultado es el conjunto de movimientos de salida de la
         *  casilla.
         * 
         * @Parámetros:
         *       cas : la casilla de origen
         * @Devuelve: Una referencia constante al conjunto de movimientos
         */ 
        const Conj<T> & Salidas(Casilla cas) const;
        
        /**
         * Devuelve las casillas que están conectadas a la casilla indicada, a
         *  través del movimiento definido.
         * 
         * PRE : La casilla pertenece al tablero.
         * POST: El resultado es el continente de la casilla.
         * 
         * @Parámetros:
         *       cas : una casilla
         *       mov : el movimiento que ingresa a cas
         * @Devuelve: Un conjunto de casillas que se llegan a 'cas' a través del
         *  movimiento 'mov'
         */ 
        Conj<Casilla> Origenes(Casilla cas, T& mov) const;
        
        /**
         * Devuelve las casillas que están conectadas a la indicada a través del
         *  movimiento definido.
         * En caso de no haber ninguna, retorna un conjunto con la propia
         *  casilla.
         * 
         * PRE : La casilla pertenece al tablero.
         * POST: El resultado es el conjunto de orígenes de 'cas' o 'cas'.
         * 
         * @Parámetros:
         *       cas : una casilla
         *       mov : el movimiento que ingresa a cas
         * @Devuelve: Un conjunto de casillas que se llegan a 'cas' a través del
         *  movimiento 'mov', o 'cas' en caso de que no haya ninguna.
         */ 
        Conj<Casilla> OrigenesR(Casilla cas, T& mov) const;

        /**
         * Devuelve el conjunto de casillas que pertenecen al Tablero.
         * 
         * PRE : Ninguna.
         * POST: El resultado es el conjunto de casillas del tablero.
         * 
         * @Parámetros: Ninguno.
         * @Devuelve: Un conjunto de casillas con todas aquellas que pertenecen
         *  al Tablero.
         */
        Conj<Casilla> Casillas() const;
        
        /**
         * Devuelve el continente al cual pertenece la casilla pasada como
         *  parámetro.
         * 
         * PRE : La casilla pertenece al tablero.
         * POST: El resultado es el continente de la casilla.
         * 
         * @Parámetros:
         *      cas: la casilla
         * @Devuelve: El continente al cual pertenece la casilla.
         */ 
        Continente ContinenteDe(Casilla cas) const;

        /**
         * Devuelve el conjunto de casillas que pertenecen al continente pasado
         *  como parámetro.
         * 
         * PRE : El continente pertenece al tablero
         * POS : El resultado es una referencia constante al conjunto de
         *  casillas del continente
         * 
         * @Parámetros:
         *      * cont: el continente para el cual se buscan las casillas
         * @Devuelve: Un conjunto de casillas, con aquellas que pertenencen al
         *  continente indicado.
         */ 
        const Conj<Casilla>& CasillasDe(Continente cont) const;

            
        /**
         * Dada una casilla devuelve un iterador a los destinos a los que puede
         *  ir desde allí.
         * 
         * PRE : La casilla forma parte del tablero.
         * POST: El resultado es un iterador a los destinos desde la casilla
         *  indicada.
         * 
         * @Parámetros:
         *       cas  : la casilla origen
         * @Devuelve: Un iterador a los destinos desde la casilla 'cas'
         *  (tupla(Casilla, Movimiento))
         */
        ItDestinos Destinos(Casilla cas) const;

        struct CasillaMov{
        
            Casilla casilla;
            T movimiento;

            CasillaMov(Casilla cas, const T& mov) : casilla(cas),
            movimiento(mov) {
            }
            
            bool operator !=(const CasillaMov cm) const{
                return (cm.casilla != casilla) || (cm.movimiento != movimiento);
            }
        };

    private:
		//ANULACION DE CONSTRUCTOR POR COPIA Y OPERADOR DE ASIGNACION
		//el constructor por copia está anulado
		Tablero(const Tablero& tab);
		
		//el operador de asignación está anulado
		Tablero & operator=(const Tablero & tab);
        
        //REPRESENTACION
        
        struct DescriptorCasilla {

            Continente continente;
            Dicc<T,Casilla> destinos;
            Conj<CasillaMov> origenes;
            Conj<T> salidas;
            
            DescriptorCasilla(Continente cont, Dicc<T,Casilla> &dests, 
            Conj<CasillaMov> & origs, Conj<T>& salds) : continente(cont),
            destinos(dests), origenes(origs), salidas(salds) {
            }
            
            DescriptorCasilla() {
            }
        };
      
        Vector<DescriptorCasilla> descCasillas;
        Vector<Conj<Casilla> > casillasContinente;



        //FUNCIONES AUXILIARES

        /**
        * Devuelve un conjunto de naturales que contiente los valores incluidos
        * entre las cotas definidas (límite inferior, lin, y límite superior,
        * lsup). Si el límite inferior es mayor o igual al límite inferior, se
        * devuelve un conjunto vacío.
        *
        * ConjRango(x): linf >= x < lsup
        *     
        * @Parámetros:
        *    lin : límite inferior
        *    lsup : límite superior
        * @Devuelve: Un conjunto de naturales con elementos entre lin y lsup
        *   (excluido)
        */
        Conj<Nat> ConjRango(Nat lin, Nat lsup) const;
        
        /**
         * Retorna el id de la proxima casilla.
         *
         * PRE : Ninguna
         * POST: Ninguna.
         *
         * @Parametros: Ninguno
         * @Devuelve: El id de la casilla
         */
        Casilla ProximaCasilla() const;
        
        /**
         * Retorna el id del proximo continente.
         *
         * PRE : Ninguna
         * POST: Ninguna.
         *
         * @Parametros: Ninguno
         * @Devuelve: El id del proximo continente
         */
        Continente ProximoContinente() const;
        
        void AgregarCasilla(Continente con);
        
      public:

        //Iterador de destinos.

        class ItDestinos{

        public:

            ItDestinos(const ItDestinos& otro) : it(otro.it) {
            
            }
            
            ItDestinos& operator=(const ItDestinos& otra) {
                it = otra.it; 
                return *this;
            }

            bool operator==(const typename Tablero<T>::ItDestinos& otro) const {
                return it == otro.it;
            }
            
            bool HaySiguiente() const;

            bool HayAnterior() const;

            CasillaMov Siguiente() const;

            CasillaMov Anterior() const;

            void Avanzar();

            void Retroceder();
        
        private:

            typename Dicc<T,Casilla>::const_Iterador  it;

            ItDestinos() {
            }
            
            ItDestinos(const Dicc<T,Casilla>& dicc);
            
            friend typename Tablero<T>::ItDestinos Tablero<T>::Destinos(Casilla)
            const;
        };

    };

    /**
    * Funciones globales de comparación.
    */
    template<class T>
    bool operator==(const Tablero<T>&, const Tablero<T>&);

    // IMPLEMENTACIÓN
    
    template<class T>
    Tablero<T>::Tablero(){
      AgregarCasilla(this->ProximoContinente());
    }

    template<class T>    
    Casilla Tablero<T>::ProximaCasilla() const {
        return this->descCasillas.Longitud();
    }
    
    template<class T>    
    Continente Tablero<T>::ProximoContinente() const {
        return this->casillasContinente.Longitud();
    }

    template<class T>
    void Tablero<T>::AgregarCasilla(Continente con) {

      Casilla cas = this->ProximaCasilla();
      
      DescriptorCasilla descCasilla;
      descCasilla.continente = con;
      this->descCasillas.AgregarAtras(descCasilla);
      
      if (con < this->ProximoContinente()) {
		  this->casillasContinente[con].AgregarRapido(cas);
      } else {
		  Conj<Casilla> c;
		  c.AgregarRapido(cas);
		  this->casillasContinente.AgregarAtras(c);
      }
    }
    
    template<class T>
    Tablero<T>::~Tablero(){
    }

    template<class T>
    void Tablero<T>::Contener(Casilla cas, T& mida, T& mvue){
    
          assert(cas < this->ProximaCasilla());
          assert(! (this->Salidas(cas)).Pertenece(mvue));

          Casilla casillaNueva  = this->ProximaCasilla();
          DescriptorCasilla descCasActual = this->descCasillas[cas];

          this->AgregarCasilla(descCasActual.continente);
          this->Conectar(casillaNueva, cas, mida, mvue);
    }

    template<class T>
    void Tablero<T>::Agregar(Casilla cas, T& mida, T& mvue){
          assert(cas < this->ProximaCasilla());
          assert(! (this->Salidas(cas)).Pertenece(mvue));

          Casilla casillaNueva = this->ProximaCasilla();
          Continente contNuevo = this->ProximoContinente();

          Conj<Casilla> casillasCont;
          casillasCont.AgregarRapido(casillaNueva);
          this->casillasContinente.AgregarAtras(casillasCont);

          DescriptorCasilla descCasNueva;
          descCasNueva.continente = contNuevo;
          descCasNueva.destinos.DefinirRapido(mida, cas);
          descCasNueva.salidas.AgregarRapido(mida);
          CasillaMov casMov(cas, mvue);
          descCasNueva.origenes.AgregarRapido(casMov);
          this->descCasillas.AgregarAtras(descCasNueva);

          DescriptorCasilla &descCasActual = this->descCasillas[cas];
          descCasActual.destinos.DefinirRapido(mvue, casillaNueva);
          descCasActual.salidas.AgregarRapido(mvue);
          CasillaMov casMov2(casillaNueva, mida);
          descCasActual.origenes.AgregarRapido(casMov2);
    }

 
    template<class T>
    void Tablero<T>::Movilizar(Casilla cas1, Casilla cas2, T& mov){
          assert(cas1 < this->descCasillas.Longitud()
            && cas2 < this->descCasillas.Longitud());
            
          assert(!(this->Salidas(cas1)).Pertenece(mov));
              
          //Se actualiza el descriptor de la casilla 1
          DescriptorCasilla &descCas1 = this->descCasillas[cas1];
          descCas1.destinos.DefinirRapido(mov, cas2);
          descCas1.salidas.AgregarRapido(mov);
          
          //Se actualiza el descriptor de la casilla existente
          DescriptorCasilla &descCas2 = this->descCasillas[cas2];
          CasillaMov casMov(cas1, mov);
          descCas2.origenes.AgregarRapido(casMov);
    }

    template<class T>
    void Tablero<T>::Conectar(Casilla cas1, Casilla cas2, T& mida, T& mvue){
		assert(cas1 < this->descCasillas.Longitud()
		&& cas2 < this->descCasillas.Longitud());

		assert(!(this->Salidas(cas1)).Pertenece(mida));
		assert(!(this->Salidas(cas2)).Pertenece(mvue));

		//Se actualiza el descriptor de la casilla 1
		DescriptorCasilla &descCas1 = this->descCasillas[cas1];
		descCas1.destinos.DefinirRapido(mida, cas2);
		descCas1.salidas.AgregarRapido(mida);
		CasillaMov casMov(cas2, mvue);
		descCas1.origenes.AgregarRapido(casMov);

		//Se actualiza el descriptor de la casilla existente
		DescriptorCasilla &descCas2 = this->descCasillas[cas2];
		descCas2.destinos.DefinirRapido(mvue, cas1);
		descCas2.salidas.AgregarRapido(mvue);
		CasillaMov casMov2(cas1, mida);
		descCas2.origenes.AgregarRapido(casMov2);
    }

    template<class T>
    Conj<Casilla> Tablero<T>::Casillas() const {
          return ConjRango(0, this->descCasillas.Longitud());
    }

    template<class T>
    Continente  Tablero<T>::ContinenteDe(Casilla cas) const {
          assert(cas < this->descCasillas.Longitud());
          return this->descCasillas[cas].continente;
    }

    template<class T>
    Conj<Casilla> Tablero<T>::Origenes(Casilla cas, T& mov) const {
          assert(cas < this->descCasillas.Longitud());
          Conj<Casilla> casOrigenes;
          typename Conj<CasillaMov>::const_Iterador iteradorOrigenes = 
            this->descCasillas[cas].origenes.CrearIt();
          
          while(iteradorOrigenes.HaySiguiente()){
          CasillaMov origen = iteradorOrigenes.Siguiente();
          if (origen.movimiento == mov)
              casOrigenes.AgregarRapido(origen.casilla);
          iteradorOrigenes.Avanzar();
          }

          return casOrigenes;
    }

    template<class T>
    Conj<Casilla> Tablero<T>::OrigenesR(Casilla cas, T& mov) const {
          assert(cas < this->descCasillas.Longitud());
          Conj<Casilla> casOrigenes = this->Origenes(cas, mov);

          if (casOrigenes.EsVacio()) {
			  casOrigenes.AgregarRapido(cas);
          }
          
          return casOrigenes;
    }


    template<class T>
    Conj<Continente> Tablero<T>::Continentes() const {
          assert(this->casillasContinente.Longitud() > 0);
          return ConjRango(0, this->casillasContinente.Longitud());
    }


    template<class T>
    bool  Tablero<T>::Conectadas(Casilla cas1, Casilla cas2) const {
        
        assert(cas1 < this->descCasillas.Longitud());
		assert(cas2 < this->descCasillas.Longitud());
      
        bool caso = this->descCasillas[cas1].salidas.Cardinal() 
            < this->descCasillas[cas2].salidas.Cardinal();

        Casilla casillaBuscada(caso ? cas2: cas1);
        typename Tablero<T>::ItDestinos itDestinos(
            caso ? this->Destinos(cas1) : this->Destinos(cas2)
        );

        while (itDestinos.HaySiguiente()) {

        	if (itDestinos.Siguiente().casilla == casillaBuscada) {
        		return true;
        	}

            itDestinos.Avanzar();
        }
          
        return false;
    }


    template<class T>
    const Conj<T> & Tablero<T>::Salidas(Casilla cas) const {
        assert(cas < this->descCasillas.Longitud());

        return this->descCasillas[cas].salidas;    
    }

    template<class T>
    const Conj<Casilla>&  Tablero<T>::CasillasDe(Continente cont) const {
        assert(cont < this->casillasContinente.Longitud());
  
        return this->casillasContinente[cont];
    }


    template<class T>
    typename Tablero<T>::ItDestinos Tablero<T>::Destinos(Casilla cas) const {
        
        assert(cas < this->descCasillas.Longitud());

        typename Tablero<T>::ItDestinos it(this->descCasillas[cas].destinos);
        return it;
    }


    template<class T>
    Conj<Nat> Tablero<T>::ConjRango(Nat lin, Nat lsup) const{

        Conj<Nat> conjRango;
          
        for (Nat i=lin; i < lsup; i++) {
            conjRango.AgregarRapido(i);
        }
    
        return conjRango;
    }
    
    
    //OPERACIONES DEL ITERADOR DE DESTINOS

    template<class T>
    Tablero<T>::ItDestinos::ItDestinos(const Dicc<T,Casilla>& diccDestinos) :
    it(diccDestinos.CrearIt()) {
    }
      
    template<class T>        
    bool Tablero<T>::ItDestinos::HaySiguiente() const {
        return this->it.HaySiguiente();
    }
    
    template<class T>
    bool Tablero<T>::ItDestinos::HayAnterior() const {
        return this->it.HayAnterior();
    }
    
    template<class T>
    typename Tablero<T>::CasillaMov Tablero<T>::ItDestinos::Siguiente() const {
        assert(this->it.HaySiguiente());

        return CasillaMov(
            this->it.SiguienteSignificado(),
            this->it.SiguienteClave()
        );
    }
    
    template<class T>
    typename Tablero<T>::CasillaMov Tablero<T>::ItDestinos::Anterior() const {
        assert(this->it.HayAnterior());
        
        return CasillaMov(
            this->it.AnteriorSignificado(),
            this->it.AnteriorClave()
        );    
    }
    
    template<class T>
    void Tablero<T>::ItDestinos::Avanzar() {
        assert(this->it.HaySiguiente());

        this->it.Avanzar();
    }
    
    template<class T>
    void Tablero<T>::ItDestinos::Retroceder() {
        assert(this->it.HayAnterior());

        this->it.Retroceder();    
    }

    template<class T>
    bool operator==(const Tablero<T>& tab1, const Tablero<T>& tab2) {

    	Conj<Casilla> casillas1 = tab1.Casillas();
    	Conj<Casilla> casillas2 = tab2.Casillas();

        if (! (casillas1.Cardinal() == casillas2.Cardinal())) {
            return false;
        }
        
        if (! (casillas1 == casillas2)) {
			return false;
		}

        Conj<Casilla>::Iterador itCas1 = casillas1.CrearIt();

        while (itCas1.HaySiguiente()) {
            Casilla c = itCas1.Siguiente();

            if (! (tab1.ContinenteDe(c) == tab2.ContinenteDe(c))) {
                return false;
            }

            if (! (tab1.Salidas(c) == tab2.Salidas(c))) {
                return false;
            }
            
            if (! (tab1.Destinos(c) == tab2.Destinos(c))) {
                return false;
            }

            itCas1.Avanzar();
        }
        
        return true;
    }

}
#endif /* __TABLERO_H__ */
